combinatoricsfandomcom-20200213-history
2929506
How to solve 4 apples, 5 oranges and 6 bananas in 4 baskets? how-to-solve-4-apples-5-oranges-and-6-bananas-in-4-baskets ( I have found a recurrence formula here : https://www.cse.iitk.ac.in/users/rgurjar/projects/CycleIndexPolynomial.pdf) The species formula for one non-empty basket is oneBasket = Ens_0^4 \ (A) \cdot Ens_0^5 \ (O) \cdot Ens_0^6 \ (B) -1 where E_0^k are sets with at most k elements. A set of four non-empty baskets is: Ens_4 \ (oneBasket) Since the parts of a partition must be non-empty, we will have to calculate four cases, from one non-empty basket to four non-empty baskets. After writing the cycle index we will extract some coefficients of \ {a^4\over 4!}{o^5\over 5!}{b^6\over 6!} \ for the e.g.f. and \ a^4o^5b^6 \ for the GF, the types generating function. 1) We write down the cycle indices of considered species Ens_0^4(A), \ Ens_0^5(O), \ Ens_0^6(B) Z(A) = 1 + a_1 + {1 \over 2!}(a_1^2 +a_2) +... {1 \over 4!}(a_1^4+...+6a_4) Z(B) = 1 + b_1 + {1 \over 2!}(b_1^2 +b_2) +... {1 \over 5!}(b_1^5+...+24b_5) Z© = 1 + c_1 + {1 \over 2!}(c_1^2 +c_2) +... {1 \over 6!}(c_1^6+...+120c_6) No further symmetric cycle indices are needed. 2) Then the cycle index of one non-empty basket is: basket (a_1,a_2,a_3,a_4;\ b_1,b_2,...,b_5;\ c_1,c_2,...,c_6) = Z(A)Z(B)Z© - 1 3) in order to make a "plethystic substitution" we need the ingredients : basket _2 = basket \ (a_2, a_4, 0, 0 \ ; \ b_2, b_4, 0, 0, 0 \ ; \ c_2, c_4, c_6,0,0,0) basket _3 = basket \ (a_3, 0, 0, 0 \ ; \ b_3, 0, 0, 0, 0 \ ; \ c_3, c_6, 0,0,0,0) basket _4 = basket \ (a_4, 0, 0, 0 \ ; \ b_4, 0, 0, 0, 0 \ ; \ c_4, 0, 0,0,0,0) 4) In the cycle index of Ens_4 {1 \over 24}(X_1^4 + 6X_1^2X_2 + 3X_2^2 + 8X_1X_3+ 6X_4) we replace X1, \ X2, \ X3, \ X4 \ with \ basket , \ basket _2, \ basket _3, \ basket _4 5) now we can extract information from the cycle index Z just obtained. Z^{types} = Z(a, a^2, a^3, a^4; \ o,o^2,...,o^5; \ b,b^2,...,b^6) is the type indicator polynomial. The coefficient of a^4o^5b^6 in Z^{types} is 5808 and it represents the number of types of partitioning the 15 mixed fruits in four nonempty baskets. 6) By repeating the above for 3,2, and one nonempty bucket we get 5808 + 1383 + 104 + 1 = 7296 7) Z^{egf} = Z(a, 0, 0,0; \ o,0,...,0; \ b,0,...0) is the e.g.f polynomial. The coefficient of {a^4\over 4!}{o^5\over 5!}{b^6\over 6!} = 42355950 in Z^{egf} represents the different distributions of 4+5+6 labelled fruits in four baskets. 8) by considering the other cases of non-empty baskets, one has : 42355950 + 2375101 + 16383 + 1 = 44747435 9) we may do some double check. For example, 1+104 = 105 means to distribute 5 oranges in two baskets in three ways : 5+0, 4+1, 3+2; then the apples and bananas multiplies the number of cases to 3.5.7= 105. 10) the 42355950 may be obtained faster by taking the coefficient of x^{15} in {1\over4!} (x + {1\over 2!}x^2 + \cdots + {1\over 15!}x^{15})^4 Indeed, when distributing labelled fruits, the colouring does not matter. Whatever comnposition of a total of 15 labelled apples, oranges and bananas will produce the same number of cases.